'''
@Author: shj
@Date: 2020-05-31 12:24:16
@LastEditTime: 2020-06-03 18:39:45
@LastEditors: shj
@Description:  反转数组中的最小值
@FilePath: /python3/algorithms/offer_code/6_the_smallest_number_of_rotate_array.py
'''
'''
题目描述
把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。
例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。
'''
'''
思路
法1：二分查找
把target(目标值) 看作是右端点
情况1，arr[mid] > target：4 5 6 1 2 3

    arr[mid] 为 6， target为右端点 3， arr[mid] > target, 说明[first ... mid] 都是 >= target 的，因为原始数组是非递减，所以可以确定答案为 [mid+1...last]区间,所以 first = mid + 1 

情况2，arr[mid] < target:5 6 1 2 3 4

    arr[mid] 为 1， target为右端点 4， arr[mid] < target, 说明答案肯定不在[mid+1...last]，但是arr[mid] 有可能是答案,所以答案在[first, mid]区间，所以last = mid; 

情况3，arr[mid] == target:

    如果是 1 0 1 1 1， arr[mid] = target = 1, 显然答案在左边
    如果是 1 1 1 0 1, arr[mid] = target = 1, 显然答案在右边
    所以这种情况，不能确定答案在左边还是右边，那么就让last = last - 1;慢慢缩少区间，同时也不会错过答案。

法2：暴力遍历
直接遍历一遍数值，得到min
'''


class Solution:
    def minNumberInRotateArray(self, rotateArray):
        # write code here
        # 数组大小为0,返回0
        if not (rotateArray):
            return 0

        (head, tail) = (0, len(rotateArray) - 1)
        while (head < tail):  # 只剩最小值
            if (rotateArray[head] < rotateArray[tail]):  # 提前退出
                break
            mid = head + (tail - head) // 2
            # 跟据旋转数组定义，提前预判最小值
            if (rotateArray[mid] < rotateArray[mid - 1]
                    and rotateArray[mid] < rotateArray[mid + 1]):
                return rotateArray[mid]
            elif (rotateArray[mid] > rotateArray[tail]):  # 情况1
                head = mid + 1
            elif (rotateArray[mid] < rotateArray[tail]):  # 情况2
                tail = mid
            else:  # 情况3
                tail -= 1
        return rotateArray[head]
